Output contest matches

Time: O(N); Space: O(N); medium

During the NBA playoffs, we always arrange the rather strong team to play with the rather weak team, like make the rank 1 team play with the rank nth team, which is a good strategy to make the contest more interesting. Now, you’re given n teams, and you need to output their final contest matches in the form of a string.

The N teams are given in the form of positive integers from 1 to N, which represents their initial rank: * Rank 1 is the strongest team and * Rank N is the weakest team.

We’ll use parentheses () and commas , to represent the contest team pairing: - parentheses () for pairing and - commas , for partition.

During the pairing process in each round, you always need to follow the strategy of making the rather strong one pair with the rather weak one.

Constraints:

  • The n is in range [2, 2^12].

  • We ensure that the input n can be converted into the form 2^k, where k is a positive integer.

Example 1:

Input: n = 2

Output: “(1,2)”

Example 2:

Input: n = 4

Output: “((1,4),(2,3))”

Explanation:

  • In the first round, we pair the team 1 and 4, the team 2 and 3 together, as we need to make the strong team and weak team together.

  • And we got (1,4),(2,3).

  • In the second round, the winners of (1,4) and (2,3) need to play again to generate the final winner, so you need to add the paratheses outside them.

  • And we got the final answer ((1,4),(2,3)).

Example 3:

Input: n = 8

Output: “(((1,8),(4,5)),((2,7),(3,6)))”

Explanation:

  • First round: (1,8),(2,7),(3,6),(4,5)

  • Second round: ((1,8),(4,5)),((2,7),(3,6))

  • Third round: (((1,8),(4,5)),((2,7),(3,6)))

[4]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(N)
    """
    def findContestMatch(self, n):
        """
        :type n: int
        :rtype: str
        """
        matches = list(map(str, range(1, n+1)))

        while len(matches)//2:
            matches = ["({},{})".format(matches[i], matches[-i-1]) for i in range(len(matches)//2)]

        return matches[0]

[7]:

s = Solution1()

n = 2
assert s.findContestMatch(n) == "(1,2)"

n = 4
assert s.findContestMatch(n) == "((1,4),(2,3))"

n = 8
assert s.findContestMatch(n) == "(((1,8),(4,5)),((2,7),(3,6)))"